/*================================================================
*   Copyright (C) 2023 baichao All rights reserved.
*
*   文件名称：main.c
*   创 建 者：baichao
*   创建日期：2023年12月28日
*   描    述：
*
================================================================*/

/*
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s
 * 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 注意： 对于 t
 * 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s
 * 中存在这样的子串，我们保证它是唯一的答案。
 *
 * 示例 1：
 *   输入：s = "ADOBECODEBANC", t = "ABC"
 *   输出："BANC"
 *   解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
 *
 * 示例 2：
 *   输入：s = "a", t = "a"
 *   输出："a"
 *   解释：整个字符串 s 是最小覆盖子串。
 *
 * 示例 3:
 *   输入: s = "a", t = "aa"
 *   输出: ""
 *   解释: t 中两个字符 'a' 均应包含在 s
 * 的子串中，因此没有符合条件的子字符串，返回空字符串。
 *
 * 提示：
 *   m == s.length
 *   n == t.length
 *   1 <= m, n <= 105
 *   s 和 t 由英文字母组成
 *
 * 进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？
 */

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

bool isContain(int32_t *stringCharCountArray, int32_t len1,
               int32_t *substringCharCountArray, int32_t len2) {
  for (int32_t i = 0; i < len2; i++) {
    if (substringCharCountArray[i] != 0 &&
        stringCharCountArray[i] < substringCharCountArray[i]) {
      return false;
    }
  }
  return true;
}

char *minWindow(char *s, char *t) {
  char *retPtr = "";
  int32_t matchingSubstringLength = 0;

  // 获取t的长度t_len
  int32_t t_len = strlen(t);
  int32_t s_len = strlen(s);

  if (s_len < t_len) return "";

  // 根据t构造子串中每个字母出现次数的数组substringCharCount。
  // A~Z:65~90; a~z:97~122;
  int32_t substringCharCountArray[58] = {0}, stringCharCountArray[58] = {0};
  for (int32_t i = 0; i < t_len - 1; i++) {
    substringCharCountArray[t[i] - 'A']++;
    stringCharCountArray[s[i] - 'A']++;
  }
  substringCharCountArray[t[t_len - 1] - 'A']++;

  // 定义一个left指针，一个right指针，均指向s字符的头，right向后移动t_len-1次，每次将所指字符写入对比数组。即将s字符串的前t_len-1个字符压入比较数组中。
  // 从s字符串的第t_len个字符串开始，每次压入一个字符后，将比较数组与待对比数组进行比较，是否相等。
  // 如果不相等，right指针就继续后移，直到s字符串的尾部。
  // 如果相等，则将left指针左移，找到最小符合子串，如果当前最小符合子串的长度（right-left）小于之前找到子串，则记录当前子串的首地址。
  char *left = s, *right = s + t_len - 1, *s_end_ptr = s + s_len - 1;
  while (right <= s_end_ptr) {
    stringCharCountArray[*(right++) - 'A']++;
    if (isContain(stringCharCountArray, 58, substringCharCountArray, 58)) {
      while (left <= right) {
        stringCharCountArray[*(left++) - 'A']--;
        if (!isContain(stringCharCountArray, 58, substringCharCountArray, 58)) {
          if (matchingSubstringLength == 0 ||
              right - left + 1 < matchingSubstringLength) {
            matchingSubstringLength = right - left + 1;
            retPtr = left - 1;
          }
          break;
        }
      }
    }
  }

  if(matchingSubstringLength != 0)
  {
    char *_retPtr = (char *)malloc(matchingSubstringLength+1);
    memcpy(_retPtr,retPtr,matchingSubstringLength);
    _retPtr[matchingSubstringLength] = 0;
    retPtr = _retPtr;
  }
  return retPtr;
}

int main() {
  char s[] = "bdab", t[] = "ab";
  char *ret = minWindow(s, t);
  printf("ret:%s\n", ret);
  return 0;
}
